#ifndef _KD_SET_H__
#define _KD_SET_H__ (1)

#include "key.h"

typedef stgKey        setkey_t;
typedef void *        setval_t;

/*************************************
 * INTERNAL DEFINITIONS
 */

/* Fine for 2^NUM_LEVELS nodes. */
#define NUM_LEVELS 20

/* Internal key values with special meanings. */
// TODO : If we need to enable week ordering, we need to define this macro constant with an appropriate value.
#define INVALID_FIELD   (0)    /* Uninitialised field value.     */
/** @brief The minimum key simply has an empty string. This is used in dummy nodes in skip-list implementation. 
*/
#define SENTINEL_KEYMIN ( stgKey("") ) /* Key value of first dummy node. */
/** @brief The maximum key has its key_ as NULL. This is used in dummy nodes in skip-list implementation. 
 */
#define SENTINEL_KEYMAX ( stgKey() ) /* Key value of last dummy node.  */


#define CALLER_TO_INTERNAL_KEY(_k) (_k)


/*
 * SUPPORT FOR WEAK ORDERING OF MEMORY ACCESSES
 */

#ifdef WEAK_MEM_ORDER

/* Read field @_f into variable @_x. */
#define READ_FIELD(_x,_f)                                       \
do {                                                            \
    (_x) = (_f);                                                \
    if ( (_x) == INVALID_FIELD ) { RMB(); (_x) = (_f); }        \
    assert((_x) != INVALID_FIELD);                              \
} while ( 0 )

#else

/* Read field @_f into variable @_x. */
#define READ_FIELD(_x,_f) ((_x) = (_f))

#endif


/*************************************
 * PUBLIC DEFINITIONS
 */


struct set_t; /* opaque */

void _init_set_subsystem(void);

/*
 * Allocate an empty set.
 */
set_t *set_alloc(void);

/*
 * Add mapping (@k -> @v) into set @s. Return previous mapped value if
 * one existed, or NULL if no previous mapping for @k existed.
 * 
 * If @overwrite is FALSE, then if a mapping already exists it is not
 * modified, and the existing value is returned unchanged. It is possible
 * to see if the value was changed by observing if the return value is NULL.
 */
setval_t set_update(set_t *s, setkey_t k, setval_t v, int overwrite);

/*
 * Remove mapping for key @k from set @s. Return value associated with
 * removed mapping, or NULL is there was no mapping to delete.
 */
setval_t set_remove(set_t *s, setkey_t k);

/*
 * Look up mapping for key @k in set @s. Return value if found, else NULL.
 */
setval_t set_lookup(set_t *s, setkey_t k);

#endif /* _KD_SET_H__ */
